class Node:#定义一个节点
    def __init__(self, data=None):
        self.data = data #元素
        self.next = None #下一个指针
        self.prev = None


class List:#定义一个单向链表
    def __init__(self):
        self.head = Node() #定义链表头 （此时的链表没有任何元素）
        self.length = 0 #链表长度为零
        self.tail = Node()
        self.head.next = self.tail.prev

    def onshift(self):#放进去
        # assert self.head == self.tail and self.head.data == self.tail.data == None or self.head != self.tail
        pass



    def shift(self):#拿出去
        pass




    def insert(self, pos, data):#指定位置插入一个元素
        assert pos >= 0 and pos <=self.length#如果列表为空，指定位置不能小于0，并且插入的位置不能比列表长度大
        if pos<=self.length//2:
            tmpPtr = self.head#把头赋给一个变量
            while pos>0:#开始查找
                tmpPtr=tmpPtr.next#确定pos前一个的节点
                pos-=1

        else:
            tmpPtr = self.head
            a = self.length
            while a > 0:
                tmpPtr = tmpPtr.next
                a -= 1
            b = self.length - pos
            while b > 0:
                tmpPtr = tmpPtr.prev
                b -= 1
        newNode = Node()#查找到之后先初始化一个节点


        if tmpPtr.next is not None:
            newNode.data = data#节点的元素赋值
            # print('{}this is newnode'.format(newNode.data))
            newNode.next =tmpPtr.next#节点指针为原来的指针
            newNode.prev = tmpPtr
            tmpPtr.next.prev = newNode
            # print('this is newNode.next'.format(newNode.next))
            tmpPtr.next = newNode#原节点的指针变为新插入的元素指针
            # print('this is tmpPtr.next'.format(tmpPtr.next))
            self.length += 1
        else:
            newNode.data = data#节点的元素赋值
            # print('{}this is newnode'.format(newNode.data))
            newNode.next =tmpPtr.next#节点指针为原来的指针
            newNode.prev = tmpPtr
            # tmpPtr.next.prev = newNode
            # print('this is newNode.next'.format(newNode.next))
            tmpPtr.next = newNode#原节点的指针变为新插入的元素指针
            # print('this is tmpPtr.next'.format(tmpPtr.next))
            self.length += 1


    def append(self,data):
        self.insert(self.length,data)

    def remove(self, pos):
        assert pos < self.length#限定删除节点在list内
        if pos<=self.length//2:
            tmpPtr = self.head
            while pos > 0:#定位要删除节点的前一个节点
                tmpPtr = tmpPtr.next
                pos -= 1
        else:
            tmpPtr = self.head
            a=self.length
            while a > 0:
                tmpPtr = tmpPtr.next
                a -= 1
            b=self.length - pos
            while b>0:
                tmpPtr = tmpPtr.prev
                b-=1

        if tmpPtr.next is not None:
            # delNode = tmpPtr.next
            # tmpPtr.next = delNode.next #也可以写作
            if tmpPtr.next.next is not None:
                tmpPtr.next = tmpPtr.next.next
                tmpPtr.next.prev = tmpPtr
                self.length -= 1
            else:
                tmpPtr.next = None
                self.length -= 1

    def foreach(self):
        if self.length<=100:
            tmpPtr = self.head.next #定位list的头
            while tmpPtr is not None:
                yield tmpPtr.data
                tmpPtr = tmpPtr.next
        else:
            tmpPtr = self.head
            pos=self.length
            while pos > 0:
                tmpPtr = tmpPtr.next
                pos -= 1
            while tmpPtr is not None:
                if tmpPtr.data is not None:
                    yield tmpPtr.data
                    tmpPtr = tmpPtr.prev


    def updata(self, pos, data):
        assert pos < self.length
        tmpPtr = self.head
        while pos >= 0:
            tmpPtr = tmpPtr.next
            pos -= 1

        if pos<self.length:
            tmpPtr.data = data


    def remove1(self,data):
        i=0
        tmpPtr = self.head
        while i<self.length:
            tmpPtr = tmpPtr.next
            if tmpPtr.data==data:
                self.remove(i)
            i+=1

    def __setitem__(self, key, value):
        assert isinstance(key, int)
        self.insert(key, value)

    def __getitem__(self, item):
        assert isinstance(item, int)
        assert item >= 0 and item < self.length

        tmpPtr = self.head.next
        while item > 0:
            tmpPtr = tmpPtr.next
            item -= 1

        return tmpPtr.data

    def __delitem__(self, key):
        assert isinstance(key, int)
        self.remove(key)

    # def __iter__(self):
    #     tmpPtr = self.head.next
    #     while tmpPtr != self.tail:
    #         yield tmpPtr.data
    #         tmpPtr = tmpPtr.next

    def __len__(self):
        return self.length


def print_iter(x):
    for v in range(0,len(x)):
        print(x[v])

if __name__ =="__main__":
    l = List()
    l.append(2)
    l.append(6)
    l.append(9)
    l.append(71)
    l.append(72)
    l.append(73)
    l.append(74)
    l.append(75)
    l.append(76)
    l.append(77)
    l.append(78)

    # print_iter(l)


    # y = (1,2,3,4)
    # l.print_iter(y)


    # for x in l.foreach():
    #     print(x)
    #
    # print("Insert new data 4")
    # l.insert(1, 4)
    l[4]=4
    for x in l.foreach():
        print(x)
    # print('=======')
    # print("Remove the 2th element")
    # # l.remove(3)
    # del l[7]
    # for x in l.foreach():
    #     print(x)
    # print('=======')
    # l.updata(1,5)
    # for x in l.foreach():
    #     print(x)
    # print(l.length)
    #
    # print('=======')
    # l.remove1(6)
    # for x in l.foreach():
    #     print(x)
    # print(l.length)









